<!DOCTYPE html>
<html lang="">
    <head><meta charset='utf-8'>
<meta name='viewport' content='width=device-width, initial-scale=1'>
<script async src="//busuanzi.ibruce.info/busuanzi/2.3/busuanzi.pure.mini.js">
</script><meta name='description' content='560. 和为 K 的子数组 题目描述： 给你一个整数数组 nums 和一个整数 k ，请你统计并返回该数组中和为 k的连续子数组的个数。 示例：
输入：nums = [1,1,1], k = 2输出：2解题思路： 通过简单分析，可以想到，把所有的连续的元素暴力穷举出来，然后让连续的元素相加等于K，最后计算有多种组合是不是就解决了这个问题。但是当数据量规模逐渐变大，我们暴力穷举就会导致花费的时间巨大。如何快速得到某个子数组的和呢，比如说给你一个数组 nums，让你实现一个接口 sum(i, j)，这个接口要返回 nums[i..j] 的和，而且会被多次调用，你怎么实现这个接口呢？那么这时就要用到前缀和的技巧了。
一、什么是前缀和 前缀和的思路是这样的，对于一个给定的数组 nums，我们开辟另外一个数组来用存储前缀的和：
int n = nums.length; // 前缀和数组 int[] preSum = new int[n &#43; 1]; preSum[0] = 0; for (int i = 0; i &amp;lt; n; i&#43;&#43;) preSum[i &#43; 1] = preSum[i] &#43; nums[i]; preSum这个数组就是我们用来存储前缀和的数据，preSum[i]中存储的就是num[0&amp;hellip;i-1]的值 ，我们想要num[i,j]的和，是不是就可以看作presum[j&#43;1]-presum[i]。 回到本题我们可以通过前缀和轻松的得到一个题解：
int subarraySum(int[] nums, int k) { int n = nums.'><title>和为K的子数组</title>

<link rel='canonical' href='http://example.org/post/2/%E5%92%8C%E4%B8%BAk%E7%9A%84%E5%AD%90%E6%95%B0%E7%BB%84/'>

<link rel="stylesheet" href="/scss/style.min.css"><meta property='og:title' content='和为K的子数组'>
<meta property='og:description' content='560. 和为 K 的子数组 题目描述： 给你一个整数数组 nums 和一个整数 k ，请你统计并返回该数组中和为 k的连续子数组的个数。 示例：
输入：nums = [1,1,1], k = 2输出：2解题思路： 通过简单分析，可以想到，把所有的连续的元素暴力穷举出来，然后让连续的元素相加等于K，最后计算有多种组合是不是就解决了这个问题。但是当数据量规模逐渐变大，我们暴力穷举就会导致花费的时间巨大。如何快速得到某个子数组的和呢，比如说给你一个数组 nums，让你实现一个接口 sum(i, j)，这个接口要返回 nums[i..j] 的和，而且会被多次调用，你怎么实现这个接口呢？那么这时就要用到前缀和的技巧了。
一、什么是前缀和 前缀和的思路是这样的，对于一个给定的数组 nums，我们开辟另外一个数组来用存储前缀的和：
int n = nums.length; // 前缀和数组 int[] preSum = new int[n &#43; 1]; preSum[0] = 0; for (int i = 0; i &amp;lt; n; i&#43;&#43;) preSum[i &#43; 1] = preSum[i] &#43; nums[i]; preSum这个数组就是我们用来存储前缀和的数据，preSum[i]中存储的就是num[0&amp;hellip;i-1]的值 ，我们想要num[i,j]的和，是不是就可以看作presum[j&#43;1]-presum[i]。 回到本题我们可以通过前缀和轻松的得到一个题解：
int subarraySum(int[] nums, int k) { int n = nums.'>
<meta property='og:url' content='http://example.org/post/2/%E5%92%8C%E4%B8%BAk%E7%9A%84%E5%AD%90%E6%95%B0%E7%BB%84/'>
<meta property='og:site_name' content='我的技术小屋'>
<meta property='og:type' content='article'><meta property='article:section' content='Post' /><meta property='article:tag' content='前缀和' /><meta property='article:published_time' content='2021-12-23T00:00:00&#43;00:00'/><meta property='article:modified_time' content='2021-12-23T00:00:00&#43;00:00'/><meta property='og:image' content='http://example.org/aa.png' />
<meta name="twitter:title" content="和为K的子数组">
<meta name="twitter:description" content="560. 和为 K 的子数组 题目描述： 给你一个整数数组 nums 和一个整数 k ，请你统计并返回该数组中和为 k的连续子数组的个数。 示例：
输入：nums = [1,1,1], k = 2输出：2解题思路： 通过简单分析，可以想到，把所有的连续的元素暴力穷举出来，然后让连续的元素相加等于K，最后计算有多种组合是不是就解决了这个问题。但是当数据量规模逐渐变大，我们暴力穷举就会导致花费的时间巨大。如何快速得到某个子数组的和呢，比如说给你一个数组 nums，让你实现一个接口 sum(i, j)，这个接口要返回 nums[i..j] 的和，而且会被多次调用，你怎么实现这个接口呢？那么这时就要用到前缀和的技巧了。
一、什么是前缀和 前缀和的思路是这样的，对于一个给定的数组 nums，我们开辟另外一个数组来用存储前缀的和：
int n = nums.length; // 前缀和数组 int[] preSum = new int[n &#43; 1]; preSum[0] = 0; for (int i = 0; i &amp;lt; n; i&#43;&#43;) preSum[i &#43; 1] = preSum[i] &#43; nums[i]; preSum这个数组就是我们用来存储前缀和的数据，preSum[i]中存储的就是num[0&amp;hellip;i-1]的值 ，我们想要num[i,j]的和，是不是就可以看作presum[j&#43;1]-presum[i]。 回到本题我们可以通过前缀和轻松的得到一个题解：
int subarraySum(int[] nums, int k) { int n = nums."><meta name="twitter:card" content="summary_large_image">
    <meta name="twitter:image" content='http://example.org/aa.png' />
    <link rel="shortcut icon" href="/img/%e7%bc%85%e5%9b%a0%e7%8c%ab.png" />
<style>
    :root {
        --article-font-family: "Noto Serif SC", var(--base-font-family);
    }
</style>

<script> 
		(function () {
		    const customFont = document.createElement('link');
		    customFont.href = "https://fonts.googleapis.com/css2?family=Noto+Serif+SC:wght@300;700&display=swap"; 
		    customFont.type = "text/css";
		    customFont.rel = "stylesheet";
		
		    document.head.appendChild(customFont);
		}());
</script>
    </head>
    <body class="
    article-page has-toc
">
    <script>
        (function() {
            const colorSchemeKey = 'StackColorScheme';
            if(!localStorage.getItem(colorSchemeKey)){
                localStorage.setItem(colorSchemeKey, "auto");
            }
        })();
    </script><script>
    (function() {
        const colorSchemeKey = 'StackColorScheme';
        const colorSchemeItem = localStorage.getItem(colorSchemeKey);
        const supportDarkMode = window.matchMedia('(prefers-color-scheme: dark)').matches === true;

        if (colorSchemeItem == 'dark' || colorSchemeItem === 'auto' && supportDarkMode) {
            

            document.documentElement.dataset.scheme = 'dark';
        } else {
            document.documentElement.dataset.scheme = 'light';
        }
    })();
</script>
<div class="container main-container flex 
    
        extended
    
">
    
        <div id="article-toolbar">
            <a href="/" class="back-home">
                <svg xmlns="http://www.w3.org/2000/svg" class="icon icon-tabler icon-tabler-chevron-left" width="24" height="24" viewBox="0 0 24 24" stroke-width="2" stroke="currentColor" fill="none" stroke-linecap="round" stroke-linejoin="round">
  <path stroke="none" d="M0 0h24v24H0z"/>
  <polyline points="15 6 9 12 15 18" />
</svg>



                <span>Back</span>
            </a>
        </div>
    
<main class="main full-width">
    <article class="has-image main-article">
    <header class="article-header">
        <div class="article-image">
            <a href="/post/2/%E5%92%8C%E4%B8%BAk%E7%9A%84%E5%AD%90%E6%95%B0%E7%BB%84/">
                
                    <img src="/aa.png" loading="lazy" alt="Featured image of post 和为K的子数组" />
                
            </a>
        </div>
    

    <div class="article-details">
    
    <header class="article-category">
        
            <a href="/categories/%E6%AF%8F%E6%97%A5%E4%B8%80%E9%A2%98/" >
                每日一题
            </a>
        
    </header>
    

    <h2 class="article-title">
        <a href="/post/2/%E5%92%8C%E4%B8%BAk%E7%9A%84%E5%AD%90%E6%95%B0%E7%BB%84/">和为K的子数组</a>
    </h2>

    

    
    <footer class="article-time">
        
            <div>
                <svg xmlns="http://www.w3.org/2000/svg" class="icon icon-tabler icon-tabler-calendar-time" width="56" height="56" viewBox="0 0 24 24" stroke-width="2" stroke="currentColor" fill="none" stroke-linecap="round" stroke-linejoin="round">
  <path stroke="none" d="M0 0h24v24H0z"/>
  <path d="M11.795 21h-6.795a2 2 0 0 1 -2 -2v-12a2 2 0 0 1 2 -2h12a2 2 0 0 1 2 2v4" />
  <circle cx="18" cy="18" r="4" />
  <path d="M15 3v4" />
  <path d="M7 3v4" />
  <path d="M3 11h16" />
  <path d="M18 16.496v1.504l1 1" />
</svg>
                <time class="article-time--published">Dec 23, 2021</time>
            </div>
        

        
            <div>
                <svg xmlns="http://www.w3.org/2000/svg" class="icon icon-tabler icon-tabler-clock" width="24" height="24" viewBox="0 0 24 24" stroke-width="2" stroke="currentColor" fill="none" stroke-linecap="round" stroke-linejoin="round">
  <path stroke="none" d="M0 0h24v24H0z"/>
  <circle cx="12" cy="12" r="9" />
  <polyline points="12 7 12 12 15 15" />
</svg>



                <time class="article-time--reading">
                    2 minute read
                </time>
            </div>
        
    </footer>
    
</div>
</header>

    <section class="article-content">
    <h1 id="560-和为-k-的子数组httpsleetcode-cncomproblemssubarray-sum-equals-k"><a class="link" href="https://leetcode-cn.com/problems/subarray-sum-equals-k/"  target="_blank" rel="noopener"
    >560. 和为 K 的子数组</a></h1>
<h2 id="题目描述">题目描述：</h2>
<p>给你一个整数数组 <code>nums</code> 和一个整数 <code>k</code> ，请你统计并返回该数组中和为 <code>k</code>的连续子数组的个数。
<strong>示例</strong>：</p>
<pre tabindex="0"><code>输入：nums = [1,1,1], k = 2
输出：2
</code></pre><h2 id="解题思路">解题思路：</h2>
<p>通过简单分析，可以想到，把所有的连续的元素暴力穷举出来，然后让连续的元素相加等于K，最后计算有多种组合是不是就解决了这个问题。但是当数据量规模逐渐变大，我们暴力穷举就会导致花费的时间巨大。<strong>如何快速得到某个子数组的和呢</strong>，比如说给你一个数组 <code>nums</code>，让你实现一个接口 <code>sum(i, j)</code>，这个接口要返回 <code>nums[i..j]</code> 的和，而且会被多次调用，你怎么实现这个接口呢？那么这时就要用到<strong>前缀和</strong>的技巧了。</p>
<h3 id="一什么是前缀和">一、什么是前缀和</h3>
<p>前缀和的思路是这样的，对于一个给定的数组 <code>nums</code>，我们开辟另外一个数组来用存储前缀的和：</p>
<div class="highlight"><pre tabindex="0" style="color:#f8f8f2;background-color:#272822;-moz-tab-size:4;-o-tab-size:4;tab-size:4"><code class="language-java" data-lang="java"><span style="color:#66d9ef">int</span> n <span style="color:#f92672">=</span> nums<span style="color:#f92672">.</span><span style="color:#a6e22e">length</span><span style="color:#f92672">;</span>
<span style="color:#75715e">// 前缀和数组
</span><span style="color:#75715e"></span><span style="color:#66d9ef">int</span><span style="color:#f92672">[]</span> preSum <span style="color:#f92672">=</span> <span style="color:#66d9ef">new</span> <span style="color:#66d9ef">int</span><span style="color:#f92672">[</span>n <span style="color:#f92672">+</span> 1<span style="color:#f92672">];</span>
preSum<span style="color:#f92672">[</span>0<span style="color:#f92672">]</span> <span style="color:#f92672">=</span> 0<span style="color:#f92672">;</span>
<span style="color:#66d9ef">for</span> <span style="color:#f92672">(</span><span style="color:#66d9ef">int</span> i <span style="color:#f92672">=</span> 0<span style="color:#f92672">;</span> i <span style="color:#f92672">&lt;</span> n<span style="color:#f92672">;</span> i<span style="color:#f92672">++)</span>
preSum<span style="color:#f92672">[</span>i <span style="color:#f92672">+</span> 1<span style="color:#f92672">]</span> <span style="color:#f92672">=</span> preSum<span style="color:#f92672">[</span>i<span style="color:#f92672">]</span> <span style="color:#f92672">+</span> nums<span style="color:#f92672">[</span>i<span style="color:#f92672">];</span>
</code></pre></div><p>preSum这个数组就是我们用来存储前缀和的数据，preSum[i]中存储的就是num[0&hellip;i-1]的值 ，我们想要num[i,j]的和，是不是就可以看作presum[j+1]-presum[i]。
回到本题我们可以通过前缀和轻松的得到一个题解：</p>
<div class="highlight"><pre tabindex="0" style="color:#f8f8f2;background-color:#272822;-moz-tab-size:4;-o-tab-size:4;tab-size:4"><code class="language-java" data-lang="java"><span style="color:#66d9ef">int</span> <span style="color:#a6e22e">subarraySum</span><span style="color:#f92672">(</span><span style="color:#66d9ef">int</span><span style="color:#f92672">[]</span> nums<span style="color:#f92672">,</span> <span style="color:#66d9ef">int</span> k<span style="color:#f92672">)</span> <span style="color:#f92672">{</span>
    <span style="color:#66d9ef">int</span> n <span style="color:#f92672">=</span> nums<span style="color:#f92672">.</span><span style="color:#a6e22e">length</span><span style="color:#f92672">;</span>
    <span style="color:#75715e">// 构造前缀和
</span><span style="color:#75715e"></span>    <span style="color:#66d9ef">int</span><span style="color:#f92672">[]</span> sum <span style="color:#f92672">=</span> <span style="color:#66d9ef">new</span> <span style="color:#66d9ef">int</span><span style="color:#f92672">[</span>n <span style="color:#f92672">+</span> 1<span style="color:#f92672">];</span>
    sum<span style="color:#f92672">[</span>0<span style="color:#f92672">]</span> <span style="color:#f92672">=</span> 0<span style="color:#f92672">;</span> 
    <span style="color:#66d9ef">for</span> <span style="color:#f92672">(</span><span style="color:#66d9ef">int</span> i <span style="color:#f92672">=</span> 0<span style="color:#f92672">;</span> i <span style="color:#f92672">&lt;</span> n<span style="color:#f92672">;</span> i<span style="color:#f92672">++)</span>
        sum<span style="color:#f92672">[</span>i <span style="color:#f92672">+</span> 1<span style="color:#f92672">]</span> <span style="color:#f92672">=</span> sum<span style="color:#f92672">[</span>i<span style="color:#f92672">]</span> <span style="color:#f92672">+</span> nums<span style="color:#f92672">[</span>i<span style="color:#f92672">];</span>

    <span style="color:#66d9ef">int</span> ans <span style="color:#f92672">=</span> 0<span style="color:#f92672">;</span>
    <span style="color:#75715e">// 穷举所有子数组
</span><span style="color:#75715e"></span>    <span style="color:#66d9ef">for</span> <span style="color:#f92672">(</span><span style="color:#66d9ef">int</span> i <span style="color:#f92672">=</span> 1<span style="color:#f92672">;</span> i <span style="color:#f92672">&lt;=</span> n<span style="color:#f92672">;</span> i<span style="color:#f92672">++)</span>
        <span style="color:#66d9ef">for</span> <span style="color:#f92672">(</span><span style="color:#66d9ef">int</span> j <span style="color:#f92672">=</span> 0<span style="color:#f92672">;</span> j <span style="color:#f92672">&lt;</span> i<span style="color:#f92672">;</span> j<span style="color:#f92672">++)</span>
            <span style="color:#75715e">// sum of nums[j..i-1]
</span><span style="color:#75715e"></span>            <span style="color:#66d9ef">if</span> <span style="color:#f92672">(</span>sum<span style="color:#f92672">[</span>i<span style="color:#f92672">]</span> <span style="color:#f92672">-</span> sum<span style="color:#f92672">[</span>j<span style="color:#f92672">]</span> <span style="color:#f92672">==</span> k<span style="color:#f92672">)</span>
                ans<span style="color:#f92672">++;</span>

    <span style="color:#66d9ef">return</span> ans<span style="color:#f92672">;</span>
<span style="color:#f92672">}</span>
</code></pre></div><p>这样写得到的题解时间复杂度为<code>O(N^2)</code> 空间复杂度 <code>O(N)</code>，并不是最优解，但这种解法是明白前缀和原理后最直观的解法，下面我们对该解法进行一个改进，因为我们得到结果的条件为</p>
<div class="highlight"><pre tabindex="0" style="color:#f8f8f2;background-color:#272822;-moz-tab-size:4;-o-tab-size:4;tab-size:4"><code class="language-java" data-lang="java"><span style="color:#66d9ef">if</span> <span style="color:#f92672">(</span>sum<span style="color:#f92672">[</span>i<span style="color:#f92672">]</span> <span style="color:#f92672">-</span> sum<span style="color:#f92672">[</span>j<span style="color:#f92672">]</span> <span style="color:#f92672">==</span> k<span style="color:#f92672">)</span>
ans<span style="color:#f92672">++;</span>
</code></pre></div><p>那么我们也可以将条件看作sum[i]-k==sum[j],这样就可以减少内层循环使时间复杂度达到 <code>O(N)</code>，因为第二层循环判断的是有几个j位置能够让’sum[i] - sum[j] == k‘。通过转移条件我们可以来找sum[j]这么大的前缀和是否存在，从而避免内层循环，可以通过用哈希表来存储前缀和以及前缀和出现的次数。</p>
<div class="highlight"><pre tabindex="0" style="color:#f8f8f2;background-color:#272822;-moz-tab-size:4;-o-tab-size:4;tab-size:4"><code class="language-java" data-lang="java"><span style="color:#66d9ef">int</span> <span style="color:#a6e22e">subarraySum</span><span style="color:#f92672">(</span><span style="color:#66d9ef">int</span><span style="color:#f92672">[]</span> nums<span style="color:#f92672">,</span> <span style="color:#66d9ef">int</span> k<span style="color:#f92672">)</span> <span style="color:#f92672">{</span>
    <span style="color:#66d9ef">int</span> n <span style="color:#f92672">=</span> nums<span style="color:#f92672">.</span><span style="color:#a6e22e">length</span><span style="color:#f92672">;</span>
    <span style="color:#75715e">// map：前缀和 -&gt; 该前缀和出现的次数
</span><span style="color:#75715e"></span>    HashMap<span style="color:#f92672">&lt;</span>Integer<span style="color:#f92672">,</span> Integer<span style="color:#f92672">&gt;</span> 
        preSum <span style="color:#f92672">=</span> <span style="color:#66d9ef">new</span> HashMap<span style="color:#f92672">&lt;&gt;();</span>
    <span style="color:#75715e">// base case
</span><span style="color:#75715e"></span>    preSum<span style="color:#f92672">.</span><span style="color:#a6e22e">put</span><span style="color:#f92672">(</span>0<span style="color:#f92672">,</span> 1<span style="color:#f92672">);</span>

    <span style="color:#66d9ef">int</span> ans <span style="color:#f92672">=</span> 0<span style="color:#f92672">,</span> sum0_i <span style="color:#f92672">=</span> 0<span style="color:#f92672">;</span>
    <span style="color:#66d9ef">for</span> <span style="color:#f92672">(</span><span style="color:#66d9ef">int</span> i <span style="color:#f92672">=</span> 0<span style="color:#f92672">;</span> i <span style="color:#f92672">&lt;</span> n<span style="color:#f92672">;</span> i<span style="color:#f92672">++)</span> <span style="color:#f92672">{</span>
        sum0_i <span style="color:#f92672">+=</span> nums<span style="color:#f92672">[</span>i<span style="color:#f92672">];</span>
        <span style="color:#75715e">// 这是我们想找的前缀和 nums[0..j]
</span><span style="color:#75715e"></span>        <span style="color:#66d9ef">int</span> sum0_j <span style="color:#f92672">=</span> sum0_i <span style="color:#f92672">-</span> k<span style="color:#f92672">;</span>
        <span style="color:#75715e">// 如果前面有这个前缀和，则直接更新答案
</span><span style="color:#75715e"></span>        <span style="color:#66d9ef">if</span> <span style="color:#f92672">(</span>preSum<span style="color:#f92672">.</span><span style="color:#a6e22e">containsKey</span><span style="color:#f92672">(</span>sum0_j<span style="color:#f92672">))</span>
            ans <span style="color:#f92672">+=</span> preSum<span style="color:#f92672">.</span><span style="color:#a6e22e">get</span><span style="color:#f92672">(</span>sum0_j<span style="color:#f92672">);</span>
        <span style="color:#75715e">// 把前缀和 nums[0..i] 加入并记录出现次数
</span><span style="color:#75715e"></span>        preSum<span style="color:#f92672">.</span><span style="color:#a6e22e">put</span><span style="color:#f92672">(</span>sum0_i<span style="color:#f92672">,</span> 
            preSum<span style="color:#f92672">.</span><span style="color:#a6e22e">getOrDefault</span><span style="color:#f92672">(</span>sum0_i<span style="color:#f92672">,</span> 0<span style="color:#f92672">)</span> <span style="color:#f92672">+</span> 1<span style="color:#f92672">);</span>
    <span style="color:#f92672">}</span>
    <span style="color:#66d9ef">return</span> ans<span style="color:#f92672">;</span>
<span style="color:#f92672">}</span>
</code></pre></div><p>最终这就是优化后的代码。</p>
<p><figure 
	>
	<a href="/%e6%8f%90%e4%ba%a4.png" >
		<img src="/%e6%8f%90%e4%ba%a4.png"
			
			
			
			loading="lazy"
			>
	</a>
	
</figure></p>

</section>


    <footer class="article-footer">
    
    <section class="article-tags">
        
            <a href="/tags/%E5%89%8D%E7%BC%80%E5%92%8C/">前缀和</a>
        
    </section>


    </footer>


    
</article>

    <aside class="related-contents--wrapper">
    
    
</aside>

     
    
        
    

    <script src="https://s3.pstatp.com/cdn/expire-1-M/jquery/3.2.1/jquery.min.js"></script>
        <script>
        function color_tags() {
            var colorArr = ["#428BCA", "#AEDCAE", "#ECA9A7", "#DA99FF", "#FFB380", "#D9B999"];
            $('.tagCloud-tags a').each(function () {
                try {
                    tagsColor = colorArr[Math.floor(Math.random() * colorArr.length)];
                    $(this).css("background", tagsColor); 
                }
                catch (err) { }
            });
        }

        $(document).ready(function () {
            color_tags()
        });
    </script>
    

    

    

    

    

    

    

    

    

    

    

    

    

    

    

    

    

    

    

    

<footer class="site-footer">
<span id="busuanzi_container_site_uv">
    本站总访问量<span id="busuanzi_value_site_uv"></span>次
</span>
    <section class="copyright">
        &copy; 
        
        2022zp妙妙屋·<i class="fas fa-bell"></i> <a id="days">0</a>Days<br>共叭叭了 3682字·共 16篇文章</br><span><p>
    </section>
    <div style="width:300px;margin:0 auto; padding:20px 0;">
    <a href="https://beian.miit.gov.cn/，" rel="external nofollow" target="_blank"><p style="float:left;height:20px;line-height:20px;margin: 0px 0px 0px 25px; color:#939393;">京ICP备2022000201号-1</p></a></span>
		 		<a target="_blank" href="http://www.beian.gov.cn/portal/registerSystemInfo?recordcode=11011102001825" style="display:inline-block;text-decoration:none;height:20px;line-height:20px;"><img src="/beian.png" style="float:left;"/><p style="float:left;height:20px;line-height:20px;margin: 0px 0px 0px 5px; color:#939393;">京公网安备 11011102001825号</p></a>
	</div>
    <section class="powerby">
        Built with <a href="https://gohugo.io/" target="_blank" rel="noopener">Hugo</a> <br />
        Theme <b><a href="https://github.com/CaiJimmy/hugo-theme-stack" target="_blank" rel="noopener" data-version="3.5.0">Stack</a></b> designed by <a href="www.zpzp.vip" target="_blank" rel="noopener">ZP</a>
    </section>
</footer>



    
<div class="pswp" tabindex="-1" role="dialog" aria-hidden="true">

    
    <div class="pswp__bg"></div>

    
    <div class="pswp__scroll-wrap">

        
        <div class="pswp__container">
            <div class="pswp__item"></div>
            <div class="pswp__item"></div>
            <div class="pswp__item"></div>
        </div>

        
        <div class="pswp__ui pswp__ui--hidden">

            <div class="pswp__top-bar">

                

                <div class="pswp__counter"></div>

                <button class="pswp__button pswp__button--close" title="Close (Esc)"></button>

                <button class="pswp__button pswp__button--share" title="Share"></button>

                <button class="pswp__button pswp__button--fs" title="Toggle fullscreen"></button>

                <button class="pswp__button pswp__button--zoom" title="Zoom in/out"></button>

                
                
                <div class="pswp__preloader">
                    <div class="pswp__preloader__icn">
                        <div class="pswp__preloader__cut">
                            <div class="pswp__preloader__donut"></div>
                        </div>
                    </div>
                </div>
            </div>

            <div class="pswp__share-modal pswp__share-modal--hidden pswp__single-tap">
                <div class="pswp__share-tooltip"></div>
            </div>

            <button class="pswp__button pswp__button--arrow--left" title="Previous (arrow left)">
            </button>

            <button class="pswp__button pswp__button--arrow--right" title="Next (arrow right)">
            </button>

            <div class="pswp__caption">
                <div class="pswp__caption__center"></div>
            </div>

        </div>

    </div>

</div><script 
                src="https://cdn.jsdelivr.net/npm/photoswipe@4.1.3/dist/photoswipe.min.js"integrity="sha256-ePwmChbbvXbsO02lbM3HoHbSHTHFAeChekF1xKJdleo="crossorigin="anonymous"
                defer="true"
                >
            </script><script 
                src="https://cdn.jsdelivr.net/npm/photoswipe@4.1.3/dist/photoswipe-ui-default.min.js"integrity="sha256-UKkzOn/w1mBxRmLLGrSeyB4e1xbrp4xylgAWb3M42pU="crossorigin="anonymous"
                defer="true"
                >
            </script><link 
                rel="stylesheet" 
                href="https://cdn.jsdelivr.net/npm/photoswipe@4.1.3/dist/default-skin/default-skin.css"integrity="sha256-c0uckgykQ9v5k&#43;IqViZOZKc47Jn7KQil4/MP3ySA3F8="crossorigin="anonymous"
            ><link 
                rel="stylesheet" 
                href="https://cdn.jsdelivr.net/npm/photoswipe@4.1.3/dist/photoswipe.css"integrity="sha256-SBLU4vv6CA6lHsZ1XyTdhyjJxCjPif/TRkjnsyGAGnE="crossorigin="anonymous"
            >

            </main>
    
        <aside class="sidebar right-sidebar sticky">
            <section class="widget archives">
                <div class="widget-icon">
                    <svg xmlns="http://www.w3.org/2000/svg" class="icon icon-tabler icon-tabler-hash" width="24" height="24" viewBox="0 0 24 24" stroke-width="2" stroke="currentColor" fill="none" stroke-linecap="round" stroke-linejoin="round">
  <path stroke="none" d="M0 0h24v24H0z"/>
  <line x1="5" y1="9" x2="19" y2="9" />
  <line x1="5" y1="15" x2="19" y2="15" />
  <line x1="11" y1="4" x2="7" y2="20" />
  <line x1="17" y1="4" x2="13" y2="20" />
</svg>



                </div>
                <h2 class="widget-title section-title">Table of contents</h2>
                
                <div class="widget--toc">
                    <nav id="TableOfContents">
  <ul>
    <li><a href="#题目描述">题目描述：</a></li>
    <li><a href="#解题思路">解题思路：</a>
      <ul>
        <li><a href="#一什么是前缀和">一、什么是前缀和</a></li>
      </ul>
    </li>
  </ul>
</nav>
                </div>
            </section>
        </aside>
    

        </div>
        <script 
                src="https://cdn.jsdelivr.net/npm/node-vibrant@3.1.5/dist/vibrant.min.js"integrity="sha256-5NovOZc4iwiAWTYIFiIM7DxKUXKWvpVEuMEPLzcm5/g="crossorigin="anonymous"
                defer="false"
                >
            </script><script type="text/javascript" src="/ts/main.js" defer></script>
<script>
    (function () {
        const customFont = document.createElement('link');
        customFont.href = "https://fonts.googleapis.com/css2?family=Lato:wght@300;400;700&display=swap";

        customFont.type = "text/css";
        customFont.rel = "stylesheet";

        document.head.appendChild(customFont);
    }());
</script>

<script
    src="https://cdn.jsdelivr.net/gh/zhixuan2333/gh-blog@v0.1.0/js/ribbon.min.js"
    integrity="sha384-UEK8ZiP3VgFNP8KnKMKDmd4pAUAOJ59Y2Jo3ED2Z5qKQf6HLHovMxq7Beb9CLPUe"
    crossorigin="anonymous"
    size="300"
    alpha="0.6"
    zindex="-1"
    defer
></script>
<script
    src="https://cdn.jsdelivr.net/gh/zhixuan2333/gh-blog@v0.1.0/js/nprogress.min.js"
    integrity="sha384-bHDlAEUFxsRI7JfULv3DTpL2IXbbgn4JHQJibgo5iiXSK6Iu8muwqHANhun74Cqg"
    crossorigin="anonymous"
></script>
<link
    rel="stylesheet"
    href="https://cdn.jsdelivr.net/gh/zhixuan2333/gh-blog@v0.1.0/css/nprogress.css"
    integrity="sha384-KJyhr2syt5+4M9Pz5dipCvTrtvOmLk/olWVdfhAp858UCa64Ia5GFpTN7+G4BWpE"
    crossorigin="anonymous"
/>
<script src="/js/snow.js"></script>
<script>
    NProgress.start();
    document.addEventListener("readystatechange", () => {
        if (document.readyState === "interactive") NProgress.inc(0.8);
        if (document.readyState === "complete") NProgress.done();
    });
</script>

    </body>
</html>
